package com.leetcode.partition3;

import java.util.Arrays;

/**
 * @author `RKC`
 * @date 2021/9/8 9:00
 */
public class LC209长度最小的子数组 {

    public static int minSubArrayLen(int target, int[] nums) {
        return prefixSum(target, nums);
    }

    public static void main(String[] args) {
        int target = 11;
        int[] nums = {1, 2, 3, 4, 5};
        System.out.println(minSubArrayLen(target, nums));
    }

    private static int prefixSum(int target, int[] nums) {
        int answer = Integer.MAX_VALUE;
        //prefix[i]记录nums[0]到nums[i-1]之和，因为都是正数，保证了其升序的性质
        int[] prefix = new int[nums.length + 1];
        for (int i = 1; i <= nums.length; i++) prefix[i] = prefix[i - 1] + nums[i - 1];
        if (prefix[nums.length] < target) return 0;

        //如果能找到两个点i和j，使得prefix[j]-prefix[i]>=target，就可以得到长度j-i
        for (int i = 0; i < prefix.length; i++) {
            //prefix[j]-prefix[i]>=target -> prefix[j]>=target+prefix[i]
            int val = target + prefix[i];
            //尝试二分查找val，如果没有查找到，则返回一个负数，这个负数取反后就是应该插入的位置
            int j = Arrays.binarySearch(prefix, val);
            if (j < 0) j = ~j;
            //需要保证j在nums的范围内
            if (j <= nums.length) {
                answer = Math.min(answer, j - i);
            }
        }
        return answer == Integer.MAX_VALUE ? 0 : answer;
    }

    private static int slidingWindow(int target, int[] nums) {
        int left = 0, right = 0, sum = 0, answer = nums.length;
        //控制右指针
        while (right < nums.length) {
            sum += nums[right];
            //如果当前窗口范围的值大于等于目标值，需要减掉左指针的值，并缩小窗口
            while (sum >= target) {
                answer = Math.min(right - left + 1, answer);
                sum -= nums[left++];
            }
            right++;
        }
        return right == nums.length && left == 0 ? 0 : answer;
    }
}
